home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / BF_SDK11.ZIP / BFCBCGR.TXT < prev    next >
Text File  |  1996-06-10  |  13KB  |  297 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.             Hinweise und Erlaeuterungen
  8.  
  9.                             zu Blowfish und CBC
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16. 1. Einleitung
  17. ~~~~~~~~~~~~~
  18.  
  19. Die Cryptengine stellt den wichtigsten Teil in einem Verschluesselungsprogramm
  20. dar. Durch sie werden Daten im RAM ver- oder entschluesselt.
  21. Sie wurde komplett in 386-Assembler entwickelt um eine maximale Bearbeitungs-
  22. geschwindigkeit zu erzielen. Durch ein klares Funktionsinterface lassen sich
  23. leicht Schnittstellen zu Hochsprachen festlegen. Mitgeliefert wird bereits
  24. eine komplett einsatzbereite Turbo-Pascal-Unit, eine INCLUDE-Datei fuer
  25. Assemblerprogramme sowie eine Headerdatei fuer C(++) Implementationen.
  26.  
  27.  
  28.  
  29. 2. Etwas Theorie...
  30. ~~~~~~~~~~~~~~~~~~~
  31.  
  32. Sinnvolle Datenverschluesslung funktioniert natuerlich nur dann,
  33. wenn der verwendete Algorithmus sicher und schnell genug ist.
  34. Diese beiden Voraussetzungen erfuellt der Blowfish-Algorithmus von Bruce
  35. Schneier. Er wurde von ihm im Fruehjahr 1994 zum ersten Mal in der
  36. Programmiererzeitschrift DDJ vorgestellt, wobei gleichzeitig zu einem
  37. Wettbewerb aufgerufen wurde, diesen neuen Algorithmus auf Schwachstellen
  38. hin zu untersuchen bzw. zu knacken. In der Septemberausgabe 1995 kam man
  39. dann zum Ergebnis, dass Blowfish in seiner jetztigen Form ungebrochen ist
  40. und es voraussichtlich auch bleiben wird.
  41.  
  42. Was macht Blowfish so attraktiv ?
  43. Neben der Sicherheit, die sowieso jedes Verschluesslungsverfahren
  44. gewaehrleisten muss, ist der grosse Vorteil die hohe Geschwindigkeit.
  45. Dies resultiert aus zwei Gruenden. Zum ersten muss im Algorithmus kein
  46. einziger Sprung durchgefuehrt werden, und zum zweiten arbeitet er intern
  47. mit 32bit-Werten. Beide Faktoren passen genau zu den Leistungsstaerken
  48. moderner Mikroprozessoren, wie z.B. i80486 oder Pentium.
  49. Blowfish ist in seinem Aufbau relativ unkompliziert. Wer die genaue
  50. Wirkungsweise nachvollziehen will lesen bitte die oben genannte Ausgaben
  51. der DDJ, oder das Buch "Applied Cryptogrphy, 2nd Edition" von Bruce Scheier.
  52.  
  53. Kurz beschrieben funktioniert der Algorithmus folgendermassen :
  54. Blowfish definiert 2 Datenstrukturen, die sogenannten Boxen. Die P-Boxen
  55. sind ein eindimensionales Feld mit 18 32bit-Werten, die S-Boxen ein
  56. zweidimensionales Feld mit 4 x 256 32bit-Werten. In Pascal formuliert
  57. sehen diese etwa so aus :
  58.  
  59.     pbox : array[1..18] of Longint;
  60.     sbox : array[1..4, 1..256] of Longint;
  61.  
  62. Ueber deren Inhalte spaeter naeheres.
  63. Verschluesselt mit Blowfish auf folgende Art und Weise : uebergeben
  64. wird ein 64bit-Datenelement (= 8 Bytes). Dieser wird zelegt in zwei Teile,
  65. nennen wir sie einmal DataLeft und DataRight, wobei DataLeft das hoeher-
  66. und DataRight das niederwertige 32bit-Wort des 64bit-Datenelements ist.
  67. Beim Verschluesseln geht mal nun folgendermassen vor :
  68.  
  69.     1:    for i:= 1 to 16 do begin
  70.     2:      DataLeft := DataLeft      XOR pbox[i];
  71.     3:      DataRight:= F(DataLeft) XOR DataRight;
  72.     4:      Swap(DataLeft, DataRight);
  73.     5:    end;
  74.  
  75. In jedem Schleifendurchgang wird zuerst DataLeft mit einem Eintrag aus
  76. den P-Boxen XORrt (2). Danach wird DataRight mit dem Ergebnis der Blowfish-
  77. funktion von DataLeft XORrt (3). Zuletzt vertauscht man die Inhalte von
  78. DataLeft und DataRigtht miteinander (4).
  79. Nach der Schleife sind noch zwei weitere Schritte noetig :
  80.  
  81.     6:    Swap(DataLeft, DataRight);
  82.     7:    DataRight:= pbox[17] XOR DataRight;
  83.     8:    DataLeft := pbox[18] XOR DataLeft;
  84.  
  85. Nun koennen DataLeft und DataRight wieder zu einem 64bit-Datenelement zusammen-
  86. gefasst werden. Da die wenigsten Prozessoren aber heute schon 64bit-Integer
  87. verarbeitet koennen uebergibt man der Ver- bzw. Entschluesselungsprozedur
  88. die beiden 32bit-Haelften direkt.
  89. Die Entschluesselungsroutine funktioniert aehnlich, nur werden hier die
  90. P-Boxen von "hinten nach vorn" benutzt :
  91.  
  92.     1:    for i:= 18 downto 3 do begin
  93.     2:      DataLeft := DataLeft      XOR pbox[i];
  94.     3:      DataRight:= F(DataLeft) XOR DataRight;
  95.     4:      Swap(DataLeft, DataRight);
  96.     5:    end;
  97.     6:    Swap(DataLeft, DataRight);
  98.     7:    DataRight:= pbox[2] XOR DataRight;
  99.     8:    DataLeft := pbox[1] XOR DataLeft;
  100.  
  101. Zu erlaeutern bleibt jetzt noch die Blowfish-Funktion F.
  102. Wie man sieht erwartet sie als Parameter einen 32bit-Wert und gibt einen
  103. solchen auch zurueck. Bei ihr kommen nun die S-Boxen ins Spiel. Der
  104. uebergebene 32bit-Wert wird in 4 Bytes aufgespalten, die ihrerseits
  105. nun Indexe auf die die 4 S-Boxen-Felder darstellen. Die jeweiligen S-Boxen
  106. werden dann in einer Funktion zu dem neuen 32bit-Wert zusammengefuegt
  107. Nennen wir die 4 Bytes a, b, c und d, den Eingabewert Input und den
  108. Rueckgabewert einfach F, dann sieht das in Pascal so aus :
  109.  
  110.     1:    d    := (Input AND $000000ff) + 1;
  111.     2:    Input:= Input SHR 8;
  112.     3:    c    := (Input AND $000000ff) + 1;
  113.     4:    Input:= Input SHR 8;
  114.     5:    b    := (Input AND $000000ff) + 1;
  115.     6:    Input:= Input SHR 8;
  116.     7:    a    := (Input AND $000000ff)+1;
  117.     8:    F    := ((sbox[1,a] + (sbox[2,b] AND $0000001f)) XOR sbox[3,c])
  118.             + ( sbox[4,d] AND $0000001f);
  119.  
  120. Man erkennt durch die vielen Binaeroperatoren SHR, AND und XOR, dass Blowfish
  121. gerade dazu praedestiniert ist in Assembler geschrieben zu werden.
  122. Bevor jedoch die Ver- und Entschluesselungsroutinen verwendet werden
  123. koennen muessen die Boxen initialisiert werden.
  124. Zuerst werden die P- und S-Boxen mit Zufallswerten gefuellt. Diese
  125. Zufallswerte werden einmal erzeugt und dann immer wieder benutzt.
  126. Der Autor von Blowfish, Bruce Schneier, verwendet dazu die hexadezimalen
  127. Werte der Kreiszahl PI. Der Vorteil ist, dass bei Verlust der Binaerdatei
  128. mit den Zufallswerten eben jene neu berechnet bzw. erzeugt werden kann.
  129. Es bleibt dem Programmierer ueberlassen, ob er die Zufallsdaten fest
  130. im Code verankert oder sie dynamisch zur Laufzeit nachlaedt.
  131. Blowfish akzeptiert Schluessel bis zu einer Laenge von 56 Bytes. Wie man
  132. den Schluessel erzeugt ist egal. Im allgemeinen wird man dazu das Passwort
  133. des Users direkt uebernehmen, jedoch sind auch andere Varianten, z.B.
  134. Hashing denkbar.
  135. Man hat also ein Feld mit einer bestimmten Anzahl von Bytes, in welchem der
  136. Key bzw. das Passwort gespeichert ist. Nun XORt man jedes Byte der P-Boxen
  137. mit einem Key-Byte. Hat man das Ende des Keys erreicht, so beginnt man wieder
  138. von vorn. In Pseudocode sieht das so aus :
  139.  
  140.         ByteZeiger = Adresse von P-Box[1]
  141.         Index = 1
  142.         for n=1 to (18*4)
  143.         begin
  144.           Inhalt von ByteZeiger = Key[Index]
  145.           ByteZeiger = ByteZeiger + 1
  146.           Index = Index + 1
  147.           if Index > (Laenge von Key) then Index = 1
  148.         end
  149.  
  150. Damit hat das Passwort seine Pflicht getan. Zuguterletzt verschluesselt man
  151. P- und S-Boxen. Dazu definiert man ein 64bit-Datenelement. Praktischerweise
  152. zerlegen wir es gleich in zwei 32bit-Haelften, wir nennen sie InitL und InitR.
  153. Man setzt beide zu Beginn auf 0 und verschluesselt dann alle Boxeneintraege
  154. mit den sich staendig aendernden zwei Haelften.
  155. Wieder in Pascal :
  156.  
  157.     1:    InitL:=0;
  158.     2:    InitR:=0;
  159.     3:    i:=1;
  160.     4:    while (i<18) do begin
  161.     5:      Encrypt(InitL, InitR);
  162.     6:      pbox[i]  :=InitL;
  163.     7:      pbox[i+1]:=InitR;
  164.     8:      i:=i+2;
  165.     9:    end;
  166.        10:    for i:=1 to 4 do begin
  167.        11:      j:=1;
  168.        12:      while (j<256) do begin
  169.        13:        Encrypt(InitL, InitR);
  170.        14:        sbox[i][j]    :=InitL;
  171.        15:        sbox[i][j+1]:=InitR;
  172.        16:        j:=j+2;
  173.        17:      end;
  174.        18:    end;
  175.  
  176. Nachteilig am Pascal ist, dass man in FOR-Schleifen den Zaehler jeweils
  177. nur um 1 erhoehen kann, deshalb muss hier auf eine WHILE-Schleife ausgewichen
  178. werden.
  179. Nach dieser Verschluesselung der Boxen ist eine Cryptengine nun einsatzbereit.
  180. Bruce Schneier erwaehnte in seinem Artikel, dass man auch die so
  181. verschluesselten Boxen abspeichern und zur spaeteren Verwendung wiederver-
  182. wenden kann (z.B. zur Schluesselweitergabe, leider nicht fuer Kommunikations-
  183. verschluesselung geeignet). Ob der Programmierer dieses Feature dem User
  184. zur Verfuegung stellt bleibt Geschmackssache.
  185.  
  186. Soviel zur Theorie des Blowfish-Algorithmus.
  187.  
  188. Das wichtigste nochmals in Kuerze :
  189.  
  190. a) dass Blowfish Daten in 64bit-Bloecken verarbeitet, d.h. es werden jedesmal
  191.    8 Bytes gleichzeitig ver- oder entschluesselt. Die Verschluesselung eines
  192.    einziges Bytes ist nicht moeglich.
  193.  
  194. b) dass Blowfish mit einem sogenannten Key initialisiert werden muss. Der Key
  195.    ist nicht anderes als das Passwort, welches der User vor der Ver- oder
  196.    Entschluesslung eingibt. Dieser Key darf maximal eine Laenge von 56 Bytes
  197.    bzw. Zeichen besitzen.
  198.  
  199. c) dass Zufallswerte benoetigt werden (genauer gesagt die mathematische 
  200.    Konstante PI in hexadezimaler Form) welche zur Initialisierung des
  201.    Algorithmus benoetigt werden. Prinzipiell koennen hier auch Zufallszahlen
  202.    aus "eigener Produktion" verwendet werden. Es hat sich jedoch als bewaehrt
  203.    erwiesen, die vorgegebenen Werte zu nehmen, da eigene Zufallszahlen z.B.
  204.    fehlerhaft sein oder bei Verlust der Quelldatei verloren gehen koennen.
  205.  
  206. An Speicherplatz ist der Algorithmus aeusserst genuegsam. Der Programmcode
  207. und die benoetigten Daten (im Fachjargon "Boxen" genannt) belegen nicht mehr
  208. als 8 Kb. Dynamische Datenstrukturen werden sowieso nicht verwendet, die
  209. Stackbelastung ist minimal.
  210. Blowfish ist symmetrisch, d.h. es wird genau so schnell ent- wie
  211. verschluesselt. Da beim Blowfish-Verfahren Zufallszahlen im Spiel sind sehen
  212. die verschluesselten Bytes ebenfalls "von aussen" zufaellig aus, d.h. jeder
  213. ASCII-Wert von 0..255 ist in einer bestimmten Datenmenge im Schnitt gleich oft
  214. enthalten, unabhaengig von der Verteilung in der originalen Datenmenge.
  215. Diese Eigenschaft zu kennen ist wichtig, da sich dadurch verschluesselte Daten
  216. nicht mehr komprimieren lassen. Wird trotzdem ein Datenkompression gewuenscht
  217. so ist sie vor der Ver- bzw. nach der Entschluesselung vorzunehmen.
  218.  
  219.  
  220.  
  221.  
  222. 3. Blowfish und noch etwas mehr - die Cryptengine
  223. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  224.  
  225. ECB-Methode:
  226. Blowfish ist ein Blockverschluesseler, d.h es werden immer 64 Bit unabhaengig
  227. voneinander bearbeitet. Diese Eigenschaft hat den Nachteil, dass man "nur"
  228. 2^64 verschiedene 64bit-Paare von unverschluesseltem und die gleiche Menge
  229. an verschluesselten Daten braucht, um dann ein Codebuch zu erstellen, d.h.
  230. jedem verschluesselten Wert eindeutig einen unverschluesselten zuweisen zu
  231. koennen. Dies ist in der Praxis natuerlich ziemlich unsinnig, denn wer hat
  232. schon 2^64*8 Bytes an Daten, in beiderlei Formen ? Doch andere
  233. cryptoanalytische Verfahren koennen darauf aufbauen und diese Schwaeche nutzen.
  234. Da die maximale Key-Lenge von Blowfish 56 Bytes (= 448 Bit) ist muessten
  235. bei einer (vollstaendigen) Brute-Force-Attack (also dem blossen Ausprobieren
  236. aller moeglichen Passwoerter) 2^448 (!) Versuche notwendig sein.
  237.  
  238. CBC-Methode:
  239. Hier greift man nun zum CBC-Verfahren um diese Sicherheitsluecke zu umgehen.
  240. Wir speichern die 64bit-Datenelemente nicht so wie sie aus der
  241. Verschluesselungsroutine herauskommen, sondern verknuepfen sie untereinander
  242. (CBC = Cipher Block Chaining -> verketten von verschluesselten Bloecken).
  243. Das CBC-Verfahren arbeitet bei Blowfish folgendermassen :
  244. Wir lassen uns zu Beginn ein 64bit-Datenelement von einem Zufallsgenerator
  245. erzeugen. Dieses nennen wir jetzt CBCStr. Wichtig ist, dass dieses Element
  246. gespeichert werden muss, z.B. im Header einer Datei. Es stellt den Beginn
  247. der Kette dar und wird zur Entschluesselung wieder benoetigt.
  248. Nach der Initialisierung des Blowfish-Algorithmus holen wird jetzt das
  249. erste 64bit-Datenelement, das wir verschluesseln wollen. Zuvor XORen wir
  250. es jedoch mit CBCStr! Jetzt erst wird das Datenelement verschluesselt und
  251. kann abgespeichert werden. Und nun der Clou : das verschluesselte Daten-
  252. element ist unser neuer CBCStr! Holen wir also das naechste
  253. 64bit-Datenelement, XORen es mit CBCStr, verschluesseln es, speichern es
  254. ab und kopieren seinen Inhalt in CBCStr, ... bis alles verschluesselt ist.
  255. Beim Entschluesseln erfolgt der Vorgang genau umgekehrt. Zuerst entschluesseln
  256. wir das erste verschluesselte 64bit-Datenelement, dann XORen wir es mit dem
  257. "Ur"-CBCStr, denn wir uns gemerkt haben. Jetzt erst koennen wir ueber die
  258. entschuesselten Daten verfuegen. Wir holen nun das zweite verschluesselte
  259. 64bit-Datenelement und entschluesseln es. Nun XORen wir es mit dem (!)
  260. verschluesselten ersten Datenelement, weil dieses ja bei der Verschluesselung
  261. der CBCStr fuer das zweite Datenelement war. Wir wiederholen diesen Vorgang
  262. bis alles entschluesselt ist. Dabei haelt man sich immer vor Augen, dass der
  263. verschluesselte Vorgaenger eines Datenelements der zugehoerige CBCStr ist.
  264. Zur Verdeutlichung noch etwas Pseudocode :
  265.  
  266.     CBC-Verschluesselung:    CBCStr = Random
  267.                 Store(CBCStr)
  268.                 while (not EndOfData)
  269.                   Read(datenelement)
  270.                   datenelement = datenelement XOR CBCStr
  271.                   Encrypt(datenelement)
  272.                   Save(datenelement)
  273.                   CBCStr = datenelement
  274.                 end
  275.  
  276.     CBC-Entschluesselung:    Restore(CBCStr)
  277.                 while (not EndOfData)
  278.                   Read(datenelement)
  279.                   Store(datenelement)
  280.                   Decrypt(datenelement)
  281.                   datenelement = datenelement XOR CBCStr
  282.                   Save(datenelement)
  283.                   Restore(datenelement)
  284.                   CBCStr = datenelement
  285.                 end
  286.  
  287. Da der allererste CBCStr bei der Verschluesselung jedesmal neu mit einem
  288. Zufallsgenerator erzeugt wird bestehen zwischen zwei urspruenglich gleichen
  289. Datenmengen in verschluesseltem Zustand dann keine Gemeinsamkeiten mehr (ein
  290. einfacher Blick in den Hex-Editor genuegt), sodass man keine einzelnen 64bit-
  291. Bloecke isolieren kann.
  292.  
  293.  
  294.  
  295. - Dokumentende -
  296.  
  297.